home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c++-part2 / 12021 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  2.0 KB
  1. Path: waichung.demon.co.uk!kyn
  2. From: Kyn Wai Chung <kyn@waichung.demon.co.uk>
  3. Newsgroups: comp.lang.c++
  4. Subject: help required on binary trees
  5. Date: Wed, 13 Mar 1996 20:53:34 +0000
  6. Organization: a
  7. Distribution: world
  8. Message-ID: <ByDMSCAOXzRxEwnw@waichung.demon.co.uk>
  9. NNTP-Posting-Host: waichung.demon.co.uk
  10. X-NNTP-Posting-Host: waichung.demon.co.uk
  11. MIME-Version: 1.0
  12. X-Newsreader: Turnpike Version 1.10 <gzdqIUQAgGCVFgCv6c5ZSzseKJ>
  13.  
  14. I require help in constructing a binary search tree in c++, as i am 
  15. relatively new to the language i am not sure how to go about
  16. implementing 
  17. it. 
  18.  Do i construct a class called btree or do i use the following:-
  19.  
  20.  struct node 
  21.   {
  22.    data  d;
  23.    struct node  *left;
  24.    struct node  *right;
  25.   }
  26.      
  27. if this is correct how do build a tree from this and insert words into
  28. it?
  29. The following is how i would implement a binary search tree in pascal.
  30. Your help will be much appreciated.
  31.  
  32. procedure BuildTree;
  33.   begin
  34.     Root := nil;
  35.     while not eof do
  36.       begin
  37.          read(NewKey);
  38.          searchAndInsert(NewKey, {starting at} Root)
  39.       end
  40.    end {BuildTree}
  41.  
  42.  
  43. procedure SearchAndInsert(NewKey : integer; {in} var Subtree : Pointer);
  44. begin
  45.    if Subtree = nil then
  46.       begin
  47.          new(SubTree);
  48.          with SubTree^ do
  49.             begin
  50.                Key := NewKey;
  51.                Left := nil;
  52.                Right := nil
  53.             end {with}
  54.       end {then statement}
  55.    else
  56.       begin
  57.          if NewKey < SubTree^.Key then
  58.             SearchAndInsert(NewKey; {in} SubTree^.Left)
  59.          elseif NewKey > SubTree^.Key then
  60.             SearchAndInsert(NewKey; {in} SubTree^.Right)
  61.          else
  62.             writeln(NewKey, ' is a duplicate entry.')
  63.       end
  64. end {SearchAndInsert}
  65.  
  66.  
  67. procedure PrintTree(Subtree : Pointer);
  68.    begin
  69.       if Subtree <> nil then
  70.          with Subtree do
  71.             begin
  72.                PrintTree(Left);
  73.                writeln(Key);
  74.                PrintTree(Right)
  75.             end
  76.    end {PrintTree}
  77.  
  78. -- 
  79. Kyn Wai Chung
  80.